class Solution {
public:
    string longestPrefix(string s) {
        string s1 = " " + s;
        vector<int> next(s1.length(), 0);
        next[0] = -1;
        int ans = 0;
        for (int i = 2, j = 0; i < s1.length(); i++) {
            while (j && s1[i] != s1[j + 1]) {
                j = next[j];
            }
            if (s1[i] == s1[j + 1]) {
                j++;
            }
            next[i] = j;
        }
        ans = next.back();
        return s.substr(0, ans);
    }
};